// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 单调栈
// 看了题解

// 执行用时：
// 12 ms
// , 在所有 C++ 提交中击败了
// 32.34%
// 的用户
// 内存消耗：
// 15.5 MB
// , 在所有 C++ 提交中击败了
// 10.55%
// 的用户

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        stack<int> sta;
        for(int i=0;i<height.size();i++){
            while (!sta.empty()&&height[sta.top()]<height[i]){
                int temp=sta.top();
                sta.pop();
                if(sta.empty()){
                    break;
                }
                int l=sta.top();
                int r =i;
                int h=min(height[l],height[r])-height[temp];
                res = res +(r-l-1)*h;
            }
            sta.push(i);
        }
        return res;
    }
};